import java.util.*;   
import java.awt.Point;  
  
public class MapGenerator {   
    private static int width;       // the width of map  
    private static int height;      // the height of map  
    private static int mapData[][] = new int[Global.TILE_AMOUNT][Global.TILE_AMOUNT];   
    private static boolean marked[][] = new boolean[Global.TILE_AMOUNT][Global.TILE_AMOUNT];
    private static Random rand= new Random(System.currentTimeMillis());  

    public static LinkedList<Point> tmppathSetING =new LinkedList<Point>();
    public static Point[][] previousNode =new Point[Global.TILE_AMOUNT][Global.TILE_AMOUNT];
    public static LinkedList<Point>  dfsPath=new LinkedList<Point>();
  
    public static int[][] getMap(int w, int h) {   
        width = w;   
        height = h;   
        mapData = new int[width][height];    
        // Initialization       
            for(int x = 0; x < width; x++) {   
            	for(int y = 0; y < height; y++) { 
                mapData[x][y] = 0;   
            }   
        }          
        mapData[0][1] = 1;
        Point a =  new Point(0,1);
        tmppathSetING.add(a);
        
        mapData[1][1] = 1;    
        a =  new Point(1,1);
        tmppathSetING.add(a);
        
        generateRoute(1, 1, 0, 1); // generating the map starting from the left-up-most ending on the right-down-most             
        return mapData;   
    }    
    
    public static void getPath(){
/*
        for(int x = 0; x < width; x++) {   
            for(int y = 0; y < height; y++) {   
               System.out.print( mapData[x][y]);   
            }   
            System.out.println();
        }   
        */
    	mapData = new int[Global.TILE_AMOUNT][Global.TILE_AMOUNT];   
        while(mapData[Global.TILE_AMOUNT-1][Global.TILE_AMOUNT-1]!=1){
        	getMap(Global.TILE_AMOUNT,Global.TILE_AMOUNT);
        }
        
        for(int i = 0;i<Global.TILE_AMOUNT;i++){
        	 for(int j = 0;j<Global.TILE_AMOUNT;j++){
        		 marked[i][j]=false;
        	 }
        }
        dfsPath=new LinkedList<Point>();
        previousNode =new Point[Global.TILE_AMOUNT][Global.TILE_AMOUNT];
        previousNode[0][1] = null;
        marked[0][1] = true;
    	dfs(0,0,new Point(0,1));
    	dfs(1,1,new Point(0,1));
    	dfs(0,2,new Point(0,1));
    	Point p = new Point(Global.TILE_AMOUNT-1,Global.TILE_AMOUNT-1);
    	while(p!=null){
    		dfsPath.push(p);
    		p = previousNode[(int)p.getX()][(int)p.getY()];
    	}
    }
    
    /*   
 		Starting from (0,0), generating the map recursively
    */   
    private static void generateRoute(int x, int y, int dx, int dy) {   
        int nextX = x + dx * 2;   
        int nextY = y + dy * 2;   
           
        // base case   
        if(nextX < 0 || nextX >= width || nextY < 0 || nextY >= height) {   
            return;   
        }   
           
        if(mapData[nextX][nextY] == 1) {    
            return;   
        }   
           
        mapData[nextX][nextY] = 1;   
        Point a =  new Point(nextX,nextY);
        tmppathSetING.add(a);
  
        mapData[x+dx][y+dy] = 1;   
        Point b = new Point(x+dx,y+dy);      
        tmppathSetING.add(b);       
        // Ending point 
        if(nextX == width - 2 && nextY == height - 2) { return; }     
        //debugOut();   
        // Choose the direction randomly  
        Vector directions = new Vector();   
        for(int i = 0; i < 4; i++) {   
            directions.addElement(new Integer(i));   
        }   
        while(!directions.isEmpty()) {   
            int index = Math.abs(rand.nextInt()) % directions.size();   
            int nextDirection = ((Integer)directions.elementAt(index)).intValue();   
            directions.removeElementAt(index);   
            switch(nextDirection) {   
                case 0: generateRoute(nextX, nextY,  1,  0); break; // move right   
                case 1: generateRoute(nextX, nextY, -1,  0); break; // move left  
                case 2: generateRoute(nextX, nextY,  0,  1); break; // move down 
                case 3: generateRoute(nextX, nextY,  0, -1); break; // move up 
            }   
        }   
    }   

    ///////////////////////////////////////////////
     


public static void dfs(int x,int y, Point p){
	previousNode[x][y] = p;
	marked[x][y] = true;
	if(x==Global.TILE_AMOUNT-1&&y==Global.TILE_AMOUNT-1)
		return;
    if(x>0){
    	if(mapData[x-1][y]==1&&!marked[x-1][y]){
    		dfs(x-1,y,new Point(x,y));
    	}
    }
    if(y>0){
    	if(mapData[x][y-1]==1&&!marked[x][y-1]){
    		dfs(x,y-1,new Point(x,y));
    	}
    }
    
    if(x<Global.TILE_AMOUNT-1){
		if(mapData[x+1][y]==1&&!marked[x+1][y]){
			dfs(x+1,y,new Point(x,y));
		}	
    }
    if(y<Global.TILE_AMOUNT-1){
    	if(mapData[x][y+1]==1&&!marked[x][y+1]){
    		dfs(x,y+1,new Point(x,y));
    	}	
    }
}  
 
//check if the four tiles around accessible
private static int f[][]={{1,-1,0,0},{0,0,1,-1}};  
public static boolean isAccessible(int x,int y,int k){  
    x+=f[0][k];  
    y+=f[1][k];  
    if((x<0)||(x>mapData[0].length-1)||(y<0)||(y>mapData.length-1)) {
    	System.out.println("is NOT Accessible +x:"+x+" y:"+y); 
    	return false;   
    }
       
    System.out.println("isAccessible +x:"+x+" y:"+y);
    return true;
} 
    
  
    /**  
        debug the map state
    */   
    public static void debugOut() {   
        System.out.println("-----------");   
        for(int y = 0; y < height; y++) {   
            for(int x = 0; x < width; x++) {   
                System.out.print(mapData[y][x]);   
            }   
            System.out.println("");   
        }   
    }   
}  